The present invention relates to a method and apparatus for generating a random number on a quantum-mechanical mechanical basis using a beam splitter.
Binary random numbers are the backbone of many encryption techniques for the secret and secure exchange of messages. Especially well known is the sole secure cryptography method in which the key is composed of a random sequence of binary zeros and ones which is as long as the binary message itself and which is only used once (xe2x80x9cone time padxe2x80x9d method). It may be that a spy who, for example, tries out all the possible keys will at some stage or other also use the correct key and decrypt the message with it. However, with the same probability, he will also obtain all manner of other possible messages of the same length, and he will not be able to discover the correct one, apart from the fact that, in the case of longer messages, the number of possible keys is astronomical and exceeds the capacity of any computer.
Random numbers are also needed for scientific and technical purposes (Monte Carlo method), but especially for games of chance. For lottery games and gambling machines, the quality of these numbers is the basis for the confidence of the players in the equipment and, therefore, is prerequisite for its economic operation. Consequently, cryptography and games of chance are dependent to a very considerable extent on the quality of random series of numbers.
Moreover, the trustworthy generation of random numbers is one of the primary tasks of a company involved in the transmission of messages.
Till now, basically two different classes of methods have been used for generating random numbers:
In algorithmic methods, a short starting sequence (seed) is used to generate a considerably longer pseudo-random sequence with the aid of mathematical operations which can be executed in software or in hardware. These pseudo-random numbers have been produced by deterministic processes in the computer, and are therefore basically not random. For many applications, however, such as for use in simulations according to the Monte Carlo method, they are sufficient and even have advantages, because they can be repeatedly generated in the same sequence. However, random-number generators designed on the basis of algorithmic methods frequently fail to satisfy the requirements of cryptography because, in the generation of the random number, there are a certain number of unusable sequences (weak keys) from the beginning, and it can be expected that there will be correlations between the random numbers.
The second class of methods for generating random numbers are physical methods. In these methods, use is made of the statistical character of certain physical processes. Generally, physical methods can be further subdivided into:
statistical processes which, although they obey deterministic equations of motion, are not predictable because of the high complexity and lack of knowledge of the initial state. Random-number generators on this basis are, for instance, the tossing of a coin xe2x80x9cheadsxe2x80x9d or xe2x80x9ctailsxe2x80x9d, or lottery machines. Such methods produce a deterministic chaos which can be considered random because, when each individual random number is generated, the starting conditions of the generator are always slightly different, without such difference being quantifiable;
fundamentally random processes (elementary processes) of the kind described by quantum mechanics. According to the present status of science, such processes cannot be attributed to hypothetical deterministic mechanisms (hidden variables), and are therefore fundamentally random by nature.
Bit sequences generated by physical processes, especially by fundamentally random quantum processes, come closer to the concept of a random sequence than algorithmically generated sequences.
The decay of radioactive atoms is a random elementary event which, owing to the high energy of the particles produced, can be easily detected and has been proposed for the generation of a random number (M. Gude: Ein quasiidealer Gleichverteilungsgenerator basierend auf physikalischen Zufallsphxc3xa4nomenen [A quasi-ideal uniform-distribution generator based on random physical phenomena], dissertation RWTH Aachen, 1987). A disadvantage in this connection, however, is the potentially harmful effect of radioactive radiation on humans and on sensitive electronic equipment.
Other physical random-number generators use physical noise sources, such as the electromagnetic noise of a resistor or diode, in order to generate random bit sequences (e.g. M. Richter: Ein Rauschgenerator zur Gewinnung von quasiidealen Zufallszahlenfxc3xcr die stochastische Simulation [A noise generator for obtaining quasi-ideal random numbers for stochastic simulation], dissertation RWTH Aachen, 1992). With these methods, however, it is often difficult for the decision threshold between bit value 1 and bit value 0 to be set precisely and invariably with respect to time. Furthermore, such random-number generators can be manipulated from outside, in that an arbitrarily selected xe2x80x9cnoisexe2x80x9d, such as that from the irradiation of electromagnetic waves, can be superimposed on the quantum noise. Since it is not easy to separate the quantum noise from this extraneous pseudo-noise, such methods are considered unsafe.
An elementary random process which has undergone careful quantum-mechanical investigation is the path selection of an individual quantum of light (photon) at a beam splitter. It is fundamentally random into which of the output channels a photon will be transferred after it strikes the beam splitter. In order to generate a random sequence, the quantum of light is reflected or transmitted, for example, at a semi-transmitting mirror, the output channels of the beam splitter each being assigned a detector which registers the quantum and whose indicator representsxe2x80x94depending on the detectorxe2x80x94the bit value 0 or 1 of the random sequence. Methods for generating random numbers on an optical basis and for the tap-proof transmission of the random code have been described, for example, in J. G. Rarity et al.: Quantum random-number generation and key-sharing, J. Mod. Opt. 41, p. 2435 (1994).
Problematic with the methods for generating a random sequence based on the individual-photon statistics at an optical beam splitter, however, are interference pulses of the detectors stemming, for instance, from cosmic radiation or other extraneous electromagnetic effects, and the low response probability of a detector to individual photons.
To date, there has been no light source which generates individual photons at identical time intervals. Previous light sources generate the photons in a random time sequence, so that it is impossible to foresee when a photon will strike the beam splitter of the optical random-number generator. This, combined with the detector noise, leads to interference pulses which are incorporated into the formation of the random sequence. In order to reduce the interference German Patent Document No. extraneous effects, it is described from DE 196 41 754.6 to employ a two-photon source as the light source in which the two photons of a photon pair are always generated approximately simultaneously. The two photons are spatially separated, one of the photons striking a trigger detector, and the other photon striking the beam splitter of the optical random-number generator. Only if the trigger responds, is the response of the detectors of the random-number generator registered. Consequently, the background due to the dark current of the detectors is reduced and the probability is increased that only those events attributable to the random-number-generating mechanism at the beam splitter will be included in the random sequence.
Basically, however, there is still the problem of the inadequate efficiency of detection of individual photons. One disadvantage of known optical random-number generators is the relatively low quantum efficiency of the detectors which are used to count the individual photons at the outputs of the beam splitter. In the best case, the quantum efficiency xcex3 for silicon detectors is xcex3=0.7 at approx. 700 nm, but this falls sharply in the infrared region of interest. Detectors for the second and third optical windows of telecommunications often have a quantum efficiency of only between 0.1 and 0.2, i.e., only one in five to one in ten photons striking the detector causes the detector to respond and leads to the generation of an output signal, and therefore of a bit value of the random sequence. In the case of a trigger detector coupled to the random-number generator according to German Patent Document No. DE 196 41 754.6, the response probability of the detector has particularly serious consequences with regard to the counting rate or speed with which a random sequence can be generated. For, since the quantum efficiency for two separate detectors which must respond simultaneously is proportional to xcex32, the counting rate is considerably lower compared to the case without a trigger.
It is proposed in German Patent Document No. DE 198 06 178.1 that, in order to increase the probability of detection, higher photon rates be used instead of one single photon, e.g., that showers of photons of n photons produced by a laser diode be employed. Problematic in this regard is the fact that all the photons of the shower of photons which strike the beam splitter must arrive in a common detector which will then, however, respond with a high probability. The probability that all the photons will arrive in a common detector is xc2xd for two photons, so that already in the case of a shower of just two photons, in half of the cases there will be no usable counting event (bit value 0 or 1 of the random sequence).
An object of the present invention, therefore, is to provide a method for generating a random number on a quantum-mechanical basis, as well as a random-number generator, in which the response probability of the detectors is increased and in which as many as possible of the particles emitted by the particle source result in a usable counting event at one of the detectors, i.e., the counting probability is increased, thus permitting the fast and reliable building of a random sequence.
The present invention provides a method and an apparatus for generating a random number using a beam splitter, whereby, due to the generation of a multi-particle state in the output channel of the beam splitter, and thus due to a plurality of particles striking on the detector, there is a significant increase in the probability of a usable counting event for each multi-particle state generated by the source. For if, within a certain time window, n photons strike the detector with a response probability y for single particles, then the n-particle response probability Pn will be:
Pn=1xe2x88x92(1xe2x88x92xcex3)nxe2x80x83xe2x80x83(1)
When using quantum pairs, the response probability of the individual detector is improved from xcex3 to (1xe2x88x92(1xe2x88x92xcex3)2). Thus, for n=2 and xcex3=0.7, the detector will already respond in over 90% of cases. If particle sources are available for number states having more than two quanta, the response probabilities can be further improved according to equation (1).
Moreover, using a multi-particle source and a beam splitter, the invention, which is described in greater detail in the following, achieves a counting probability of one, i.e., each particle pair from the source passes to only one detector; no particle pair is split at the beam splitter.
The starting point of the present invention is the generation of a random number on the basis of the quantum statistics of individual particles at a beam splitter. According to the present invention, first of all, a multi-particle state with at least two quantum-mechanically correlated particles is generated, the individual particles being emitted in at least partially different spatial directions, and therefore traversing different beam-component paths.
The particles are preferably photons originating, for example, from an optical cascade transition or from parametric fluorescence. It is also advantageous to employ a particle source which is a photon-pair source, in particular a non-linear optical crystal in conjunction with a pumping light source, such as a laser. Through parametric conversion, one pumped photon will, with certain probability, result in the generation of two fluorescent photons in a quantum-mechanically entangled state with correlated energy, polarization and defined spatial emission distribution. Parametric fluorescence is particularly suitable for the present invention, since in this case, the photons of a photon pair can be easily coupled into the beam-component paths because of the spatial emission distribution. Likewise, existing background radiation, in particular the pumping light, can be suppressed to a great extent by spatial shutters or masks, spectral filters and polarizers.
It is also advantageously possible to use a squeezed-light source as the particle source. The photons generated by it are likewise correlated with each other in pairs.
Instead of photons, it is also possible to employ atoms or other quantum particles. In analogy to light optics, xe2x80x9copticalxe2x80x9d elements are also known for atoms, such elements having the properties of a beam splitter, polarizer, mirror, detector, etc.
A special quantum-mechanical characteristic of the particles which are in a quantumxe2x80x94mechanically entangled state is their ability, like wave amplitudes, to interfere with each other as particles. Although the overall intensities are always positive, there are arrangements in which the intensities of two photons or other quanta are added to form zero, i.e., interfere each other away. Because of the conservation of energy, such anti-correlations cause the pair-wise occurrence of the photons elsewhere. This characteristic is used according to the present invention to cause a particle pair, in which the two partners are not collinear, at a beam splitter to always leave the beam splitter as a pair in one of the two outputs.
Therefore, after the generation of the multi-particle state, particularly of a photon pair, in contrast to the process disclosed in German Patent Document No. DE 196 41 754.6, one of the particles is not coupled into a trigger channel and detected, but rather both or all particles are coupled into generally different input channels of a beam splitter and brought to interference at the beam splitter. Provided for this purpose are particle-deflecting elements, such as mirrors, prisms, lenses and the like, which are disposed in one or all of the beam-component paths. The respective beam-component paths of the random-number generator are preferably of approximately identical optical length, in order to ensure that the particles are able to interfere with each other at the beam splitter. To precisely match the lengths, it is possible to provide adjusting elements which are electrically controllable. Likewise, one of the beam-component paths is preferably provided with a variable delay section, e.g., with an optical trombone slide.
Also provided is at least one particle-influencing element which is tunable and is positioned in a beam-component path-length. By tuning this element, it is ensured according to the present invention that all the particles at the beam splitter are directed into a common output channel of the beam splitter and therefore strike on the detector allocated to this output channel. The response probability of the detector is increased by the substantially simultaneous impact of at least two particles.
The detectors are adapted to the particles emitted by the particle source. In the case of a random-number generator on an optical basis, the detectors are photodetectors which are matched to the wavelength, e.g., infrared detectors. Single-photon detectors, especially avalanche diodes, are particularly advantageous in this case.
Preferably, the particle-influencing element is tuned in that the coincidences between the outputs of the beam splitterxe2x80x94i.e., between the detectors allocated to the outputsxe2x80x94are measured and minimized. Given approximately identical transit times of the particles in the beam-component paths, the disappearance of coincidences means that the particles leave the beam splitter via a common output. However, it is also possible to calculate what setting of the elements positioned in the beam-component paths will lead to the minimization of the coincidences, and for that setting to be selected accordingly. In the latter case, under certain circumstances, it may only be necessary to readjust the apparatus for the actual minimization of the coincidences.
The particle-influencing element is preferably an interferometer, in particular a Mach-Zehnder interferometer, a Michelson interferometer or a Fabry-Perot interferometer or an echelon. The interferometer may also be a linearly double-refractive crystal, preferably a xcex/2 plate matched to the wavelength of the light passing through the interferometer. To increase the path difference, in the last-mentioned case, the interferometer can include a compensator, in particular a Babinet-Soleil compensator or an electrically tunable delay plate such as a liquid-crystal cell, Kerr cell or the like.
In one advantageous refinement of the invention, the path-length difference of the interferometer exceeds the coherence length of the photons by a multiple. This prevents the particle passing through the interferometer from interfering with itself. In this embodiment of the present invention, the optical path length of the one beam-component path, averaged over the interferometer arms, is substantially identical with the optical path length of the other beam-component path, and the path-length difference in the interferometer is preferably a whole-number multiple of the mean wavelength of the photons emitted by the particle source. In this case, the probability of coincidences between the outputs of the beam splitter is theoretically zero, so that, in practice, a large proportion of all photon pairs leave the beam splitter spatially as a pair, thus increasing the response probability of the respective detector.
Likewise, given correct tuning of the elements, none of the photon pairs is split at the beam splitter. This prevents the photons of a pair from causing both detectors to respond and thereby produce counting events which do not correspond to an unambiguous bit value of 0 or 1. In order to suppress any response of both detectors nevertheless occurring and to discard such response for the generation of a random number, provision is preferably made for an anti-coincidence circuit which only evaluates a counting event of a detector if the other detector has not registered a particle within a defined time window.
In the event that a source of multi-photon number states is available, the individual state is, in turn, split and dropped on the two inputs of the beam splitter. Due to the particle interference, the photons all leave the beam splitter in one output and are detected as in the two-particle case. The more photons leave the beam splitter in one arm and are simultaneously detected, the higher is the counting efficiency of the detectors according to equation (1).